package com.cty.twentyFifthDay;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

//给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
public class Q_36 {
    public static void main(String[] args) {
        TreeNode treeNode1 = null;
//        TreeNode treeNode2 = new TreeNode(2);
//        TreeNode treeNode3 = new TreeNode(3);
//        treeNode1.right = treeNode2;
//        treeNode2.left = treeNode3;
        Q_36 q_36 = new Q_36();
        List<Integer> integers = q_36.inorderTraversal(treeNode1);
        integers.forEach(System.out::println);
    }

    List<Integer> ans = new ArrayList<>();

    // 通过时间复杂度O(n) 空间复杂度O(n) 用到了栈
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) return new ArrayList<>();
        if (root.left != null) {
            inorderTraversal(root.left);
        }
        ans.add(root.val);
        if (root.right != null) {
            inorderTraversal(root.right);
        }
        return ans;
    }

    // 力扣官方题解 方法一:递归
    /*
     * 时间复杂度O(n)
     * 空间复杂度O(n)
     * */
    public List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        inorder(root, ans);
        return ans;
    }

    private void inorder(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }
        inorder(node.left, list);
        list.add(node.val);
        inorder(node.right, list);
    }

    // 力扣官方题解 方法二:迭代
    /*
     * 思路:
     *   用栈来解决问题
     *   首先将左子节点全部压入栈内
     *   之后再取出栈中的元素加入
     *   结果集中，然后再遍历右子
     *   节点
     *   时间复杂度O(n) 空间复杂度O(n)
     * */
    public List<Integer> inorderTraversal3(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        // 创建一个栈
        Deque<TreeNode> stk = new LinkedList<>();
        while (root != null || !stk.isEmpty()) {
            while (root != null) {
                stk.push(root);
                root = root.left;
            }
            TreeNode pop = stk.pop();
            ans.add(pop.val);
            root = pop.right;
        }
        return ans;
    }


    // 力扣官方题解 方法三:Morris 中序遍历
    /*
    * 思路:
    *  predecessor节点 就是当前节点的左子树的最右节点的右节点 指向自己
    *   当predecessor节点 被遍历到的时候说明当前节点的左子树已经被遍历完了
    *   所以断开该节点 遍历右子树
    *   时间复杂度O(n) 空间复杂度O(1)
    * */
    public List<Integer> inorderTraversal4(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        TreeNode predecessor;
        while (root != null) {
            // 先判断左子树是否存在
            if (root.left != null) {//存在则设置 predecessor
                predecessor = root.left;
                while(predecessor.right != null && predecessor.right != root) {
                    predecessor = predecessor.right;
                }
                //该判断说明没有开始遍历左子树 所以设置predecessor然后开始遍历
                if (predecessor.right == null) {
                    predecessor.right = root;
                    root = root.left;
                } else {
                    // 说明 predecessor左子树已经访问完了
                    ans.add(root.val);
                    predecessor.right = null;
                    root = root.right;

                }
            } else {
                ans.add(root.val);
                root = root.right;
            }
        }
        return ans;
    }
}
